'''
    中缀表达式转后缀表达式：A * B + C * D-->AB*CD*+
        1. 创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。
        2. 通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
        3. 从左到右扫描标记列表。
           - 如果标记是操作数，将其附加到输出列表的末尾。
           - 如果标记是左括号，将其压到 opstack 上。
           - 如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
           - 如果标记是运算符，`*，/，+`或 `-` ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。
        4. 当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
    该算法的具体实现还是参考文档说明，更详细一些。作用比较大。
'''
from Stack import Stack

# 创建优先级词典
def creatPrec():
    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1
    return prec

# 中缀表达式转前缀表达式：从右往左读取表达式,就是一个反转再转过来
def infixToPrefix(infixexpr):
    prec = creatPrec()  # 创建运算符优先级字典
    opstack = Stack()   # 创建运算符栈
    prefixList = [] # 前缀表达式列表
    tokenList = infixexpr.split()
    tokenList.reverse()
    #print(tokenList)

    for token in tokenList: # 倒叙读取中缀表达式
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':  # 操作数添加到输出列表
            prefixList.append(token)
        elif token == ')':  # 右括号操作符
            opstack.push(token)
        elif token == '(':  # 左括号要找到右括号，需要退栈
            topToken = opstack.pop()
            while topToken != ')':
                prefixList.append(topToken)
                topToken = opstack.pop()
        else:   # 其他的操作符号
            while (not opstack.isEmpty()) and (prec[token] <= prec[opstack.peek()]):    # 操作符优先级低
                prefixList.append(opstack.pop())    # 操作符加入前缀列表
            opstack.push(token)

    while not opstack.isEmpty():
        prefixList.append(opstack.pop())    # 操作符加入前缀列表

    return ' '.join(reversed(prefixList))

# 中缀表达式转后缀表达式：从左到右读取表达式
def infixToPostfix(infixexpr):
    prec = creatPrec()  # 创建运算符优先级映射字典
    opstack = Stack()   # 创建运算符栈
    postfixList = []    # 后缀表达式列表
    tokenList = infixexpr.split()   # 前缀表达式切分为列表

    for token in tokenList:
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':  # 操作数加到输出列表
            postfixList.append(token)
        elif token == '(':
            opstack.push(token) # 左括号入栈
        elif token == ')':  # 右括号出栈，直到遇到（
            topToken = opstack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opstack.pop()    # 接着出栈
        else:
            while (not opstack.isEmpty()) and (prec[token] <= prec[opstack.peek()]):    # 入栈的优先级低，下面的栈要出栈(算法规则)
                postfixList.append(opstack.pop())
            opstack.push(token)

    while not opstack.isEmpty():
        postfixList.append(opstack.pop())   # 最后栈里的运算符都要出栈

    return ' '.join(postfixList) # 合并列表为字符串，中间填充空格

# 前缀表达式转中缀表达式：
def prefixToInfix(prefixExpr):
    prec = creatPrec()  # 创建运算符优先级字典
    tokenList = prefixExpr.split()
    tokenList.reverse()
    infixStack = Stack() # 中缀表达式存储栈
    operatorList = []   # 操作符列表，每个操作符以列表形式存储[操作符，位置]
    index = 0
    count = 0
    biaozhi = False # 是否加括号

    for token in tokenList:
        count = count + 1 # 每个符号的下标
        if token in '+-*/':
            list1 = [token,count]
            operatorList.append(list1)
    #print(operatorList)

    for token in tokenList:
        if token in '0123456789' or token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':  # 操作数
            infixStack.push(token)
        else:   # 操作符
            for i in range(index,len(operatorList)):
                if (prec[operatorList[i][0]] > prec[token]) and (operatorList[i][1] - operatorList[index][1] != 3):
                    biaozhi = True
            op1 = infixStack.pop()
            op2 = infixStack.pop()
            res = doTO(token,op1,op2,biaozhi)
            infixStack.push(res)
            biaozhi = False
            index = index + 1
    return infixStack.pop()

# 后缀表达式转中缀表达式：
def postfixToInfix(prefixExpr):
    prec = creatPrec()  # 创建运算符优先级字典
    tokenList = prefixExpr.split()
    infixStack = Stack() # 中缀表达式存储栈
    operatorList = []   # 操作符列表，每个操作符以列表形式存储[操作符，位置]
    index = 0
    count = 0
    biaozhi = False # 是否加括号

    for token in tokenList:
        count = count + 1 # 每个符号的下标
        if token in '+-*/':
            list1 = [token,count]
            operatorList.append(list1)
    #print(operatorList)

    for token in tokenList:
        if token in '0123456789' or token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':  # 操作数
            infixStack.push(token)
        else:   # 操作符
            for i in range(index,len(operatorList)):
                if (prec[operatorList[i][0]] > prec[token]) and (operatorList[i][1] - operatorList[index][1] != 3):
                    biaozhi = True
            op2 = infixStack.pop()
            op1 = infixStack.pop()
            res = doTO(token,op1,op2,biaozhi)
            infixStack.push(res)
            biaozhi = False
            index = index + 1
    return infixStack.pop()

# 关于前后缀表达式之间的相互转换，我没有观察到直接的算法，但是可以通过前后缀和中缀的相互转化进行转化，问题一点也不大，很好计算。

def doTO(op,op1,op2,biaozhi):
    if biaozhi:
        return '(' + op1 + op + op2 +')'
    else:
        return op1 + op + op2



# 计算前缀表达式的值
def prefixEval(prefixExpr):
    oprandStack = Stack() # 操作数
    tokenList = prefixExpr.split()
    tokenList.reverse()

    for token in tokenList:
        if token in '0123456789':
            oprandStack.push(int(token))
        else:
            oprand1 = oprandStack.pop()
            oprand2 = oprandStack.pop()
            res = doMath(token,oprand1,oprand2)
            oprandStack.push(res)
    return oprandStack.pop()

# 后缀表达式求值：借助后缀表达式进行求值比较简单，遇到运算符计算栈上的两个值并返回结果存入栈即可。后面我要写前缀表达式
'''
    1. 创建一个名为 `operandStack` 的空栈。
    2. 拆分字符串转换为标记列表。
    3. 从左到右扫描标记列表。
       - 如果标记是操作数，将其从字符串转换为整数，并将值压到operandStack。
       - 如果标记是运算符`*，/，+`或` - `，它将需要两个操作数。弹出operandStack 两次。 第一个弹出的是第二个操作数，第二个弹出的是第一个操作数。执行算术运算后，将结果压到操作数栈中。
    4. 当输入的表达式被完全处理后，结果就在栈上，弹出 operandStack 并返回值。
'''
def postfixEval(postfixExpr):
    operandSrack = Stack()  # 创建新栈
    tokenList = postfixExpr.split()

    for token in tokenList:
        if token in '0123456789':
            operandSrack.push(int(token))
        else:
            operand2 = operandSrack.pop()
            operand1 = operandSrack.pop()
            res = doMath(token,operand1,operand2)
            operandSrack.push(res)
    return operandSrack.pop()

def doMath(op,operand1,operand2):
    if op == '*':
        return operand1 * operand2
    elif op == '/':
        return operand1 / operand2
    elif op == '+':
        return operand1 + operand2
    elif op == '-':
        return operand1 - operand2





if __name__ == '__main__':  # 该算法实际上是对列表按照一定规则进行的排序，以后若遇到合适的需要栈来排序的大概都可以利用此方法
    # print(infixToPostfix("A * B + C * D"))
    # print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
    # print(postfixEval('7 8 + 3 2 + /'))
    # print(infixToPrefix("A * B + C * D"))
    # print(prefixEval('- * 2 5 * 1 5'))
    print(prefixToInfix('- * 2 5 * 1 5'))
    print(postfixToInfix('1 3 5 * + 7 9 / -'))
    print(postfixToInfix('1 3 5 * 7 9 / - *'))

